package com.cb2.algorithm.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * <a href='https://leetcode.cn/problems/4sum'>四数之和(4Sum)</a>
 * <p>给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
 *  <ul>
 *      <li>0 <= a, b, c, d < n</li>
 *      <li>a、b、c 和 d 互不相同</li>
 *      <li>nums[a] + nums[b] + nums[c] + nums[d] == target</li>
 *  </ul>
 * </p>
 * <p>你可以按 任意顺序 返回答案 。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 *  示例 1：
 *      输入：nums = [1,0,-1,0,-2,2], target = 0
 *      输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
 *
 *  示例 2：
 *      输入：nums = [2,2,2,2,2], target = 8
 *      输出：[[2,2,2,2]]
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>1 <= nums.length <= 200</li>
 *     <li>-10^9 <= nums[i] <= 10^9</li>
 *     <li>-10^9 <= target <= 10^9</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @see LC0018_4Sum_M 四数之和
 * @see LC0454_4Sum_II_M 四数相加 II
 * @since 2025/2/7 13:58
 */
public class LC0018_4Sum_M {
    static class Solution {
        public List<List<Integer>> fourSum(int[] nums, int target) {
            List<List<Integer>> resList = new ArrayList<>();
            if (nums == null || nums.length < 4) {
                return resList;
            }
            Arrays.sort(nums);
            int length = nums.length;
            for (int i1 = 0; i1 < length-3; i1++) {
                // 第一层去重
                int first = nums[i1];
                if (i1 > 0 && first == nums[i1 - 1]) {
                    continue;
                }
                // == first是固定的，second、third、fourth是待选的
                // 如果此次循环，second、third、fourth取最小的三个数，四数之和都大于target，那么任意的second、third、fourth得到的和也都大于target。
                // 此时需要减小first，又因first不支持减小，所以后续计算无意义，退出本层循环
                if ((long) first + nums[i1 + 1] + nums[i1 + 2] + nums[i1 + 3] > target) {
                    break;
                }
                // 如果此次循环，second、third、fourth取最大的三个数，四数之和都小于target，那么任意的second、third、fourth得到的和也都小于target。
                // 此时需要增大first，跳出本次循环
                if ((long) first + nums[length - 3] + nums[length - 2] + nums[length - 1] < target) {
                    continue;
                }
                for (int i2 = i1 + 1; i2 < length - 2; i2++) {
                    // 第二层去重
                    int second = nums[i2];
                    if (i2 > i1 + 1 && second == nums[i2 - 1]) {
                        continue;
                    }
                    // == first、second是固定的。third、fourth是待选的
                    // 如果此次循环，third、fourth取最小的两个数，四数之和都大于target，那么任意的third、fourth得到的和也都大于target。
                    // 此时需要减小second，又因second不支持减小，所以后续计算无意义，退出本层循环
                    if ((long) first + second + nums[i2 + 1] + nums[i2 + 2] > target) {
                        break;
                    }
                    // 如果此次循环，third、fourth取最大的两个数，四数之和都小于target，那么任意的third、fourth得到的和也都小于target。
                    // 此时需要增大second，跳出本次循环
                    if ((long) first + second + nums[length - 2] + nums[length - 1] < target) {
                        continue;
                    }
                    int i3 = i2 + 1;
                    int i4 = length - 1;
                    while (i3 < i4) {
                        long sum = (long) first + second + nums[i3] + nums[i4];
                        if (sum < target) {
                            ++i3;
                        } else if (sum > target) {
                            --i4;
                        } else {
                            resList.add(Arrays.asList(first, second, nums[i3++], nums[i4--]));
                            // 第三层、第四层去重
                            while (i3 < i4 && nums[i3] == nums[i3 - 1]) {
                                ++i3;
                            }
                            while (i3 < i4 && nums[i4] == nums[i4 + 1]) {
                                --i4;
                            }
                        }
                    }
                }
            }
            return resList;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        Printer.printListListInteger(solution.fourSum(new int[]{1, 0, -1, 0, -2, 2}, 0));
        Printer.printListListInteger(solution.fourSum(new int[]{2, 2, 2, 2, 2}, 8));
    }
}
